package sword.chapter3String;

/**
 * 字符串中的变位词
 * <p>
 * 输入两个字符串s1和s2，如何判断s2中是否包含s1的某个变位词？
 * 如果s2中包含s1的某个变位词，则s1至少有一个变位词是s2的子字符串。
 * 假设两个输入字符串中只包含英语小写字母。例如输入字符串s1为"ab"，s2为"dgcaf"，由于s2中包含s1的变位词"ba"，因此输出是true。
 * 如果输入字符串s1为"ac"，s2为"dcgaf"，输出为false。
 * <p>
 * 变位词：1字母出现次数相同 2单词长度相同
 * 要点：
 * 1. 数组下标记录字母出现次数，出现+1 去掉-1。然后第一步以s1开始计算，后面以s2计算
 * 2. 双指针记录s2
 *
 * @author K
 * @date 2021-11-13 15:23
 */
public class S14CheckInclusion {

    public static void main(String[] args) {
        String s1 = "ac";
        String s2 = "dgcaf";
        boolean result = checkInclusion(s1, s2);
        System.out.println();
    }

    public static boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        int[] counts = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            counts[s1.charAt(i) - 'a']++;
            counts[s2.charAt(i) - 'a']--;
        }
        if (checkAllZero(counts)) {
            return true;
        }
        for (int i = s1.length(); i < s2.length(); i++) {
            counts[s2.charAt(i) - 'a']--;
            counts[s2.charAt(i - s1.length()) - 'a']++;
            if (checkAllZero(counts)) {
                return true;
            }
        }
        return false;
    }

    private static boolean checkAllZero(int[] counts) {
        for (int count : counts) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }
}
